原题链接: https://codeforces.com/contest/1325/problem/C
题目大意:
给你一颗n个节点的树,要求你给树上的n-1条边确定边权,满足以下条件
①每个分配的边权取值范围是[0,n-2]
②所有边权都是唯一的,不会重复出现
③对于树上任意两个节点u&v,满足最大的MEX(u,v)最小
定义:MEX(u,v) = 在u到v简单通路上,没有出现的最小的非正整数
数据范围:
2 <= n <= 1e5
分析:
题目要求的是最大的MEX(u,v)最小,先来考虑如何让MEX(u,v)最小,但是在这之前先来考量另一个问题:MEX最小能到多少?如何能达到?
首先题目中要求的是任意两个点的MEX值,最后在这个集合里面拿最小值出来,所以极端的个例是不用考虑的;如果我们想要构造一种情况使得MEX值能够尽量的小,那么这种构造方式一定是让最小的数先来构造的:也就是0 1 2 3这几个点中去考虑:我们知道MEX值是定义在路径上没有出现过的最小的数,那么我们不让最小的几个数出现在任意两点u和v的联通路径上不就能把MEX的值降低了吗?由此可以大概的想到这个题的构造方式就在于让最小的几个数不同时出现在一条路径上,只要不同时出现在一条路径上就一定可以使答案是这几个很小的数。
其次我们缩小考虑范围:对于0和1这两个数来说,他们俩一定会在一条路径上,无论你怎样构造,0和1一定会导致MEX的最终结果至少是2。而如果要让答案比2大的话,则路径上一定要同时存在0,1,2。所以我们只要让0,1,2不同时出现在一条联通的路径上,就可以使得整个树上的MEX值不超过2。
这个摆放方式就是类似下图:
并且这三个特定的边权的摆放方式没有要求。
解决了特定的边权摆放方式,使得MEX最小的构造方式已经想完了,接下来的问题是树的形态是什么:
①假如一颗树退化成了一条链,那么我们无论怎么构造数据其实都是无用功,因为选取首尾两端的点所得的MEX一定是最大的,并且值一定是n-1,对于退化成一条链的情况我们直接输出一种结果就可以了。
②树没退化(只要有任意一个点的度>=3就没有退化),那么一定有一个节点的度是3,也就是说一定可以找到一条节点,它联通了3条边,只要我们把0,1,2三个特定的值放上去就可以了;其余的随意摆放。
至此整个问题就解决了,剩下还有一个边角问题:题目中给的输入是一条边联通u和v,输出的时候要求按输入的顺序输出每条边的边权,这里有个写法就是把读入的u和v不直接联通而是联通当前是哪条边的编号"i"(这里是使用vector来存)
也就是edge[u].push_back(i),edge[v].push_back(i);实际要存答案的时候直接用
res[edge[i][0/1/2]] ,节点i联通的第1/2/3条边即输入时边的顺序编号,直接写入答案输入res即可。具体见代码即可
代码:https://codeforces.com/contest/1325/submission/73321990
